n=100;
m=100;
road=[|1,2,5|
2,3,4|
3,4,4|
4,5,4|
5,6,4|
6,7,4|
7,8,4|
8,9,4|
9,10,4|
10,11,4|
11,12,5|
12,13,5|
13,14,4|
14,15,5|
15,16,5|
16,17,4|
17,18,5|
18,19,4|
19,20,4|
20,21,5|
21,22,5|
22,23,4|
23,24,4|
24,25,4|
25,26,4|
26,27,5|
27,28,4|
28,29,5|
29,30,5|
30,31,5|
31,32,4|
32,33,5|
33,34,5|
34,35,5|
35,36,4|
36,37,4|
37,38,4|
38,39,5|
39,40,4|
40,41,4|
41,42,4|
42,43,5|
43,44,4|
44,45,5|
45,46,4|
46,47,4|
47,48,5|
48,49,4|
49,50,4|
50,51,5|
51,52,4|
52,53,5|
53,54,5|
54,55,4|
55,56,4|
56,57,4|
57,58,4|
58,59,5|
59,60,5|
60,61,4|
61,62,5|
62,63,4|
63,64,5|
64,65,5|
65,66,4|
66,67,5|
67,68,5|
68,69,4|
69,70,4|
70,71,5|
71,72,5|
72,73,4|
73,74,4|
74,75,5|
75,76,5|
76,77,5|
77,78,5|
78,79,4|
79,80,5|
80,81,4|
81,82,4|
82,83,4|
83,84,4|
84,85,4|
85,86,5|
86,87,4|
87,88,4|
88,89,4|
89,90,4|
90,91,5|
91,92,4|
92,93,5|
93,94,5|
94,95,5|
95,96,4|
96,97,5|
97,98,5|
98,99,4|
99,100,5|];
plans=[|39,72|
1,34|
29,62|
40,73|
41,74|
63,96|
23,56|
10,43|
56,89|
31,64|
49,82|
42,75|
64,97|
19,52|
50,83|
27,60|
67,100|
42,75|
28,61|
29,62|
7,40|
52,85|
5,38|
14,47|
45,78|
66,99|
48,81|
31,64|
10,43|
24,57|
8,41|
32,65|
49,82|
56,89|
67,100|
24,57|
45,78|
67,100|
66,99|
10,43|
54,87|
37,70|
28,61|
5,38|
24,57|
40,73|
26,59|
18,51|
55,88|
28,61|
8,41|
11,44|
1,34|
16,49|
48,81|
49,82|
46,79|
49,82|
9,42|
45,78|
4,37|
53,86|
17,50|
2,35|
12,45|
61,94|
20,53|
64,97|
35,68|
31,64|
42,75|
32,65|
1,34|
44,77|
29,62|
57,90|
54,87|
66,99|
62,95|
36,69|
29,62|
50,83|
32,65|
8,41|
6,39|
1,34|
23,56|
66,99|
29,62|
54,87|
39,72|
27,60|
65,98|
11,44|
52,85|
10,43|
20,53|
2,35|
66,99|
55,88|];